package leetcode_1000;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author 周杨
 * 2019年6月16日 下午3:53:53
 * LargestValuesFromLabels_1090.java
 * description: 给两个数组 第一个表示值 第二个表示它是第几类的 然后再给两个正整数 第一个表示 最多需要选n个数来构成集合 第二个表示这n个数里每一组的个数不超过m 用贪心算法
 */
public class LargestValuesFromLabels_1090 {
	class Help {
		int value;
		int label;
		public Help(int value,int label) {
			this.value = value;
			this.label = label;
		}
	}

	public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
		PriorityQueue<Help> heap = new PriorityQueue<>((o1,o2)->o2.value-o1.value);
		for(int i=0;i<values.length;++i) {
			Help now = new Help(values[i],labels[i]);
			heap.add(now);
		}
		int res = 0;
		int total = 0;
		Map<Integer,Integer> record = new HashMap<Integer,Integer>();
		while(!heap.isEmpty()) {
			Help now = heap.poll();
			Integer count = record.get(now.label);
			if(count == null) {
				res += now.value;
				++total;
				if(num_wanted == total) return res;
				record.put(now.label, 1);
			}else {
				if(count == use_limit) continue;
				else {
					res += now.value;
					++total;
					if(num_wanted == total) return res;
					record.put(now.label, count+1);
				}
			}
		}
		return res;
	}
}
